package leetcode.code198;

/**
 * 递归
 *
 * @author 瓦师傅
 * @date 2021年8月6日
 * @description
 */
public class Solution5 {

	public static void main(String[] args) {
		int[] nums = { 1, 2, 3, 1 };
		int[] nums1 = { 2, 7, 9, 3, 1 };
		int[] nums2 = { 2, 1, 4, 5, 3, 1, 1, 3 };
		int[] nums3 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
				0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
		Solution5 solution = new Solution5();
		int result = solution.massage(nums3);
		System.out.println(result);
	}

	public int massage(int[] nums) {
		int[] dp = new int[nums.length];
		return massage(nums, 0, dp);
	}

	/**
	 * 从position开始的最大和
	 *
	 * @param nums
	 * @param position
	 * @return
	 */
	private int massage(int[] nums, int position, int[] dp) {
		if (position >= nums.length) {
			return 0;
		}
		if (dp[position] != 0) {
			return dp[position];
		}
		int sumy = nums[position] + massage(nums, position + 2, dp);
		int sumn = massage(nums, position + 1, dp);
		if (sumy > sumn) {
			dp[position] = sumy;
		} else {
			dp[position] = sumn;
		}
		return dp[position];
	}
}
